package personal.leil.learning.lessmoney;

import java.util.PriorityQueue;

/**
 * 金条切割问题
 * <p>
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。
 * 一群人想整分整块金条，怎么分最省铜板?
 * 例如,给定数组{10,20,30]，代表一共三个人，整块金条长度为10+20+30=60。金条要分成10,20,30三个部分。
 * 如果先把长度60的金条分成10和50，花费60;再把长度50的金条分成20和30，花费50;一共花费110铜板。
 * 但是如果先把长度60的金条分成30和30，花费60:再把长度30金条分成10和20.花费30;一共花费90铜板。
 * <p><i>输入一个数组，返回分割的最小代价</i></p>
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024/1/26
 */
public class LessMoney {


    /**
     * 使用哈夫曼树思想解决问题
     *
     * @param arr 最终拆分结果数组
     * @return [花费，总量]
     */
    public static int[] process(Integer[] arr) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (Integer num : arr) {
            queue.offer(num);
        }
        int result = 0;
        while (queue.size() > 1) {
            Integer num1 = queue.poll();
            Integer num2 = queue.poll();
            queue.offer(num1 + num2);
            result = result + num1 + num2;
        }
        return new int[]{result, queue.poll()};
    }


    /************* For Test ********************/
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{10, 30, 50, 40, 20};
        int[] results = process(arr);
        System.out.println(results[0]);
        System.out.println(results[1]);
    }

}
